﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

using SharedGenomics.Core.Collections;
using SharedGenomics.Annotations;

namespace SharedGenomics.Workbench.Annotations
{
    public class StaticAnnotationPlanFactory : IAnnotationPlanFactory
    {
        private readonly IAnnotationManager _annotationManager;
        private readonly AnnotationKeyDependencyGraphProvider _dependencyGraphProvider;

        public StaticAnnotationPlanFactory(IAnnotationManager annotationManager, AnnotationKeyDependencyGraphProvider dependencyGraphProvider)
        {
            this._annotationManager = annotationManager;
            this._dependencyGraphProvider = dependencyGraphProvider;
        }

        public IAnnotationPlan CreatePlan()
        {
            //get the required annotations from the annotation manager
            IEnumerable<AnnotationKey> keys = this._annotationManager.ActiveAnnotationDescriptors.Select(ad => ad.Key).ToList();

            //get the dependency graph
            var dependencyGraph = this._dependencyGraphProvider.GetRequestDependencyGraph();

            //build plan tree and plan
            var planTree = this.BuildPlan(keys, dependencyGraph);
            return new StaticAnnotationPlan(planTree);
        }

        private Tree<AnnotationKey> BuildPlan(IEnumerable<AnnotationKey> requiredAnnotations, AnnotationKeyDependencyGraph annotationDependencies)
        {
            Debug.Assert(requiredAnnotations != null);
            Debug.Assert(annotationDependencies != null);

            Tree<AnnotationKey> planTree = new Tree<AnnotationKey>();

            //go through each required annotation key and find a path from that node to a root (i.e. annotation with no dependencies) in the graph
            //once this path has been found it should be added to the current plan
            foreach (AnnotationKey currentKey in requiredAnnotations)
            {
                //get node from the dpenedency graph and find a path to a parent node
                var keyNode = annotationDependencies.GetNodeForKey(currentKey);
                var path = this.GetPathToAnnotation(keyNode);

                this.AddToPlan(planTree, path);
            }

            //at this stage the plan tree has been constructed, however it may not be in the correct order. The plan will be traversed pre-order i.e. 
            //root -> left subtree -> right subtree. We want the 'quickest' annotations to be completed first and these are assumed to be the ones with the 
            //fewest number of dependencies (i.e. those higher up the tree). The FinialisePlan method will re-order the child nodes in the tree such that 
            //the shallowest subtrees are on the left.
            this.FinalisePlan(planTree);

            return planTree;
        }

        private Stack<AnnotationKey> GetPathToAnnotation(AnnotationKeyDependencyNode keyNode)
        {
            Debug.Assert(keyNode != null);

            //we walk the graph backwards (target -> dependency) but the requests must be added to the plan forwards
            Stack<AnnotationKey> dependencyPath = new Stack<AnnotationKey>();

            dependencyPath.Push(keyNode.Value);
            AnnotationKeyDependencyNode currentNode = keyNode.Parent;

            while (currentNode != null)
            {
                dependencyPath.Push(currentNode.Value);
                currentNode = currentNode.Parent;
            }

            return dependencyPath;
        }

        private void AddToPlan(Tree<AnnotationKey> planTree, Stack<AnnotationKey> keyPath)
        {
            Debug.Assert(planTree != null);
            Debug.Assert(keyPath != null);

            //first key in the path should be the root key
            //NOTE: path should always contain at least one item
            Debug.Assert(keyPath.Count > 0);
            AnnotationKey rootKey = keyPath.Pop();

            //if the tree is empty the first item in the path must be the root
            if (planTree.Root == null)
            {
                planTree.Root = new TreeNode<AnnotationKey>(rootKey);
            }

            Debug.Assert(planTree.Root.ValueEquals(rootKey));

            TreeNode<AnnotationKey> currentParent = planTree.Root;

            //add the minimal required subtree to the plan tree to add the target annotation (keyPath.Last()) to the plan
            while (keyPath.Count > 0)
            {
                AnnotationKey currentKey = keyPath.Pop();

                //see if the current stage of the path is a child of the current parent node
                var currentPathNode = currentParent.GetChildByValue(currentKey);

                if (currentPathNode == null)
                {
                    //stage does not exist so create it
                    currentParent = currentParent.AddChild(currentKey);
                }
                else
                {
                    //current path stage already exists in the plan
                    currentParent = currentPathNode;
                }
            }
        }

        private void FinalisePlan(Tree<AnnotationKey> planTree)
        {
            Debug.Assert(planTree != null);

            if (planTree.Root != null)
            {
                this.ReOrderPlanStageNode(planTree.Root);
            }
        }

        private int ReOrderPlanStageNode(TreeNode<AnnotationKey> node)
        {
            //re-order all subtrees and collect their max distances from the current node to a leaf
            List<int> subTreeDepths = node.Children.Select(c => this.ReOrderPlanStageNode(c)).ToList();

            //order the children of this node such that shallower subtrees are to the left
            //create a mapping subTreeDepth -> index
            var depthMap = Enumerable.Range(0, subTreeDepths.Count).Select(i => new KeyValuePair<int, int>(subTreeDepths[i], i)).ToList();

            //sort map on subtree depth
            depthMap.Sort((x, y) => x.Key.CompareTo(y.Key));

            //set node child ordering
            node.SetChildOrder(depthMap.Select(m => m.Value).ToList());

            //return the distance from this node to the deepest leaf node
            int maxDepth = subTreeDepths.Count == 0 ? 0 : subTreeDepths.Max();
            return 1 + maxDepth;
        }
    }
}
